import java.util.HashMap;
import java.util.Map;

/**
 * @author 汤奇
 * @version V1.0
 * @Project BookPro
 * @Package PACKAGE_NAME
 * @Description:
 * @Date 2022/7/25 19:10
 */
public class Test03 {
    public static void main(String[] args) {
//        Node<Integer> top = new Node<>();
//        top.value = 1;
//        top.next = new Node<>();
//        top.next.value = 2;
//        top.next.next = new Node<>();
//        top.next.next.value = 3;
//        top.next.next.next = new Node<>();
        Node<Integer> top = new Node<>();
        Node<Integer> p = top;
        for (int i = 1; i < 10; i++) {
            p.value = i;
            if (i == 9){
                break;
            }
            //重点
            p.next = new Node<>();
            p = p.next;
        }
        print(top);

        //链表2,3中间插入元素
        //让指针重新指向1
        p = top;
        //创建要插入的元素
        Node<Integer> temp = new Node<>();
        //给元素赋值
        temp.value = 100;
        //先让temp指向2,顺序不能错
        p = p.next;
        temp.next = p.next;
        //再让2指向temp
        p.next = temp;
        print(top);

        //链表的删除操作
        p = top;
        p = p.next;
        //跳过p的下一个元素, 即跳过100这个元素
        p.next = p.next.next;
        temp = null;
        print(top);

        //做一个循环链表
        //找到链表的尾节点, 让它的下一个指向top;
        for (;;){
            if (p.next!=null){
                p = p.next;
            } else {
                break;
            }
        }
        //让它的尾节点指向top
        p.next = top.next.next.next.next;
        if (f2(top)){
            System.out.println("链表带环");
        } else {
            print(top);
        }

        System.out.println("环的切入点为:"+f3(top).value);
        System.out.println("环的切入点为:"+f4(top).value);

    }

    /**
     * 如果一个链表有环,求环的大小
     * @param top
     * @return
     */
    //todo: 没做
    private static int f5(Node top){
        Node p1 = top;
        Node p2 = top;

        for (;;){
            if (p2.next == null || p2.next.next == null){
                return 0;
            }
            p1 = p1.next;
            p2 = p2.next.next;

            if (p1 == p2){
                p1 = top;
                if (p1 == p2){
                    return (int) (p1.value);
                } else {
                    p1 = p1.next;
                    p2 = p2.next;
                }
            }
        }
    }

    /**
     * 如果链表带环, 就求出环的切入点
     * @param top 链表的头节点
     * @return 返回切入点或者null
     */
    private static Node f3(Node top){
        Map<Node,Void> cache = new HashMap<>();
        Node p = top;
        for (;;){
            if (p.next != null){
                cache.put(p,null);
                p = p.next;
            } else {
                return null;
            }

            if (cache.containsKey(p)){
                return p;
            }
        }
    }

    private static Node f4(Node top){
        Node p1 = top;
        Node p2 = top;

        for (;;){
            if (p2.next ==null || p2.next.next == null){
                //走的快的指针走到头了
                return null;
            }

            p1 = p1.next;
            p2 = p2.next.next;

            if (p1 == p2){
                p1 = top;
                for (;;){
                    if (p1 == p2){
                        return p1;
                    } else {
                        p1 = p1.next;
                        p2=p2.next;
                    }
                }
            }
        }
    }

    private static boolean f2(Node top){
        Node p1 = top;
        Node p2 = top;


        for (;;){
            if (p2.next == null || p2.next.next == null){
                //快的指针先走到头
                return false;
            }
            p1 = p1.next;
            p2= p2.next.next;

            if (p1 == p2){
                return  true;
            }

        }
    }

    private static boolean f1(Node top){
        Map<Node,Void> cache = new HashMap<>();
        Node p = top;
        for (;;){
            if (p.next != null){
                //记录p的路径历史
                cache.put(p,null);
                p = p.next;
            } else {
                return false;
            }

            if (cache.containsKey(p)){
                return true;
            }
        }
    }
    /**
     * 判断链表是否带环
     * @param top
     * @return
     */
    private static boolean f (Node top){
        Node p = top;
        for (;;){
            if (p.next != null){
                p = p.next;
            } else {
                return false;
            }
            if (p == top){
                return true;
            }
        }
    }

    public static void print(Node top){
        //循环遍历链表
        //让指针重新指向1
        Node p = top;
        for (;  ; ) {
            if (p == null){
                break;
            }
            System.out.print(p.value+" ");
            p = p.next;
        }
        System.out.println();
    }

    static class Node<T>{
        T value;
        Node<T> next;
    }
}
